class Node{
    public int key;
    public int val;
    public Node next;
    public Node(int key,int val){
        this.key=key;
        this.val=val;
    }
}
public class HashBuck {
    public Node[] elem;
    public int usedSize;
    public HashBuck(){
        this.elem=new Node[10];
    }

    public static final double DEFAULT_LOAD_FACTOR=0.75;

    public void put(int key,int val){
        int index=key%elem.length;
        Node cur=elem[index];
        while(cur!=null){
            if(cur.key==key){
                cur.val=val;
                break;
            }
            cur=cur.next;
        }
        Node node=new Node(key,val);
        node.next=elem[index];
        elem[index]=node;
        usedSize++;
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            resize();
        }
    }

    private double loadFactor(){
        return 1.0*usedSize/elem.length;
    }

    public void resize(){
        Node[]newelem=new Node[2*elem.length];
        for (int i = 0; i < elem.length; i++) {
            Node cur=elem[i];
            while(cur!=null){
                int index=cur.val%newelem.length;
                Node curNext=cur.next;
                cur.next=newelem[index];
                newelem[index]=cur;
                cur=cur.next;
            }
        }
        elem=newelem;
    }


    public int get(int key){
        int index=key%elem.length;
        Node cur=elem[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }

    public static void main(String[] args) {
        HashBuck hashBuck=new HashBuck();
        hashBuck.put(1,1);
        hashBuck.put(12,11);
        hashBuck.put(33,33);
        hashBuck.put(22,22);
        hashBuck.put(40,40);
        hashBuck.put(41,41);
        hashBuck.put(1,1);
        hashBuck.put(8,8);
        hashBuck.put(12,12);
        hashBuck.put(20,20);
        hashBuck.put(4,4);
        System.out.println("===");
        System.out.println(hashBuck.get(1));
    }

}
